#==================================
#            定义一些函数
#==================================
# 函数 inside(set1,set2)判断两个集合是否存在包含关系
# set1，set2为两个集合
def inside(set1,set2): 
    return (set1|set2==set1)|(set1|set2==set2)

# 函数 combine(ListSets)返回列表中所有集合的并集
# ListSets为列表类型，列表元素为集合类型
def combine(ListSets):
    cset=ListSets[0]
    for subset in ListSets:
        cset=cset|subset
    return cset

# 函数DeleteSubset(ListSets)对一组集合进行精简，使集合数目最小化
# 首先删去其中被其余集合所包含的集合，然后删去多余的集合(删去不影响并集结果)
# 输入ListSets为列表类型，列表元素为集合类型
# 返回精简后的集合列表
def DeleteSubset(ListSets):
    #删除被包含的集合
    over=False
    while not over:
        over=True
        N=len(ListSets) #当前集合列表的集合数目
        for i in range(N-1,0,-1):
            set1=ListSets[i]
            for set2 in ListSets[:i]:
                if inside(set1,set2):
                    over=False
                    ListSets.pop(i)
                    break
    #删除多余的集合
    over=False
    while not over:
        over=True
        N=len(ListSets) #当前集合列表的集合数目
        for i in range(N-1,0,-1):
            if combine(ListSets)==combine(ListSets[:i]+ListSets[i+1:]):
                over=False
                ListSets.pop(i)
    return ListSets

# 函数Findset(base,set)
# 用于在基础集合列表base中找出合并出目标集合set的最佳方式(基础集合数最少)
def Findset(base,set):
    # 首先找出在base中所有set的子集
    sub_base=[k for k in base[::-1] if (k|set)==set]   
    # 然后删除这些子集中存在包含关系的子集
    return DeleteSubset(sub_base)

# 函数GenerateSet(N1,N2,k)  递归
# 用递归方法从N1-N2的自然数中挑选k个元素所组成的所有可能集合
# 返回集合列表，包含个CkN2-N1+1个集合，每个集合包含k个元素
def GenerateSet(N1,N2,k):
    if k==1:
        return [{i} for i in range(N1,N2+1)]
    else:
        sets=[]
        for i in range(N1,N2+2-k):
            for subset in GenerateSet(i+1,N2,k-1):
                sets+=[{i}|subset]
        return sets

# 函数GenerateSet1(code)  由编码产生集合
# code为整数，比如，5，对应的二进制码为000...00101
# 那么由此产生集合{1,3}
# 返回一个集合
def GenerateSet1(code):
    TransCode=list('{:018b}'.format(code))
    oneset=set()
    for k in range(-1,-len(TransCode)-1,-1):
        if TransCode[k]=='1':
            oneset|={-k}
    return oneset

#==================================
#            主程序
#==================================
# 基础集合
base=[{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11},{12},{13},{14},{15},{16},{17},{18},
      {1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{13,14},{15,16},{17,18},
      {1,3,5},{2,4,6},{7,9,11},{8,10,12},{13,15,17},{14,16,18},
      {1,7,13},{3,9,15},{5,11,17},{2,8,14},{4,10,16},{6,12,18},
      {1,3,5,7,9,11,13,15,17},{2,4,6,8,10,12,14,16,18},
      {1,2,3,4,5,6},{7,8,9,10,11,12},{13,14,15,16,17,18},
      {1,2,7,8,13,14},{3,4,9,10,15,16},{5,6,11,12,17,18}]
# 计数器，初始为零
counter=18*[0]
# 两种方式择其一来遍历所有集合：递归和编码
'''
# 递归方式产生集合
for k in range(1,18):  #考虑从1-18中挑选1~17个元素组成集合的情况
    Sets=GenerateSet(1,18,k)
    for EachSet in Sets:
        num=len(Findset(base,EachSet))  #每个集合最少需要多少个基础集合来合成
        counter[num-1]+=+1
'''
# 编码方式遍历所有集合
for code in range(1,2**18-1):
    EachSet=GenerateSet1(code)
    num=len(Findset(base,EachSet))
    counter[num-1]+=+1

counter[0]+=2          #单独考虑空集和全集的情况
for k in range(18):
    print('最少需要%d个合取式来合成的假设数目：%d'%(k+1,counter[k]))
    